Матч 226, Движение по Манхетену (ManhattanMovement)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 1

Вы находитесь в городе в точке (x₀, y₀) и вам разрешено двигаться в любом из четырех направлений параллельно осям координат. В любой точке пути можно изменять направление движения на одно из четырех допустимых. В городе имеется дорога в виде бесконечной прямой, уравнение которой имеет вид: ax + by = 1. Вам необходимо выйти на эту дорогу по кратчайшему пути.

Класс: ManhattanMovement

Метод: double getDistance(int a, int b, int x0, int y0)

Ограничения: a и b одновременно не равны нулю.

Вход. Целые чсла a, b, x0, y0.

Выход. Длина кратчайшего пути, которым можно выйти из точки (x₀, y₀) на дорогу, заданную уравнением ax + by = 1.

Пример входа

a	b	x0	y0
1	2	-2	3
37	37	42	19
-100	0	-999999	314159

Пример выхода

1.5

60.97297297297297

999998.99

РЕШЕНИЕ

геометрия

Для решения задачи следует заметить, что для выхода на дорогу достаточно выбрать правильное направление и идти нигде не сворачивая. Если прямая ax + by = 1 имеет горизонтальный или вертикальнаый вид, то достаточно выбрать направление непосредственно к ней, которое будет допустимым. Если прямая не параллельна ни одной из осей координат, то достаточно вычислить расстояние до нее в горизонтальном и вертикальном направлениях и найти среди них наименьшее.

ПРОГРАММА

#include <stdio.h>

#include <math.h>

class ManhattanMovement

{

public:

double getDistance(int a, int b, int x0, int y0)

{

double t1, t2;

if (!a) return fabs(1.0 / b - y0);

if (!b) return fabs(1.0 / a - x0);

t1 = fabs((1 - (double)a * x0) / b - y0);

t2 = fabs((1 - (double)b * y0) / a - x0);

return (t1 < t2) ? t1 : t2;

}

};